# -*- coding: utf-8 -*-
u"""2017.6.3 算法."""
from random import randint, seed
from copy import deepcopy
from ticktock import ticktock


class Algorithm(object):
    u"""学习算法的综合类."""

    def __init__(self, size=100):
        u"""初始化，set seed 生成所需的随机序列."""
        seed(2)
        self.random_list = [randint(0, size) for x in range(size)]

    def sum(self, target):
        u"""递归的加法."""
        # 因为长度为1了，就只剩下最后一个元素了，就直接干脆，返回这个元素得了
        if len(target) == 1:
            return target[0]
        else:
            # 其他情况下，将第一个元素从列表中pop出去，并且与下一层返回的结果相加
            return target.pop(target[0]) + self.sum(target)

    @ticktock(begin=True)
    @staticmethod
    def binary_search(ordered_list, target):
        u"""二分法的算法."""
        # 指定最大的和最小的index
        small = 0
        large = len(ordered_list) - 1

        # freq 返回计算次数
        freq = 0
        results = None
        # 当小值＜大值才是正常的
        while small <= large:
            # 无论到哪都需要做的几步
            freq += 1
            mid = (small + large) // 2
            # 根据比较得来的大小进行替换，上下限值
            """
            2017.6.3 还是书上的写的更完善
            首先应当判断是否满足最终条件
            最后用一个else来handle所有的剩余情况
            再有这里确实不应该直接将mid的值赋给其他变量，而是应当变化一下
            没有变化就逼不出异常，逼不出异常状态，我们的各种判断就没有作用了
            """
            if target == ordered_list[mid]:
                results = mid
                break
            if target < ordered_list[mid]:
                large = mid - 1
            else:
                small = mid + 1
        return results, freq

    @staticmethod
    @ticktock(begin=False)
    def bubble_sort(target):
        u"""冒泡排序."""
        # 深度copy一下，防止为后边对同一个序列做多次排序，进行算法速度的比较
        """
        冒泡排序就是一个双层嵌套循环
        让所有的值，一一比较过去，没有任何偷懒的余地，保证所有的值都比对一遍
        应当是一个O(n!)层级的算法
        也就是要求巨严格的时候用用
        """
        target = deepcopy(target)
        for i in range(len(target) - 1):
            for j in range(i, len(target)):
                if target[i] > target[j]:
                    target[j], target[i] = target[i], target[j]

        return target

    @staticmethod
    @ticktock(begin=False)
    def selection_sort(target):
        u"""选择排序."""

        """
        选择排序，O(n log(n))层级的算法
        每次都找到最小的那一个， 然后将原本list中的元素挪到新的list中，
        这样，越往后越快，因为需要遍历找的最小元素越少
        """
        target = deepcopy(target)
        def find_smallest(list_):
            u"""返回最小的那个元素的index."""
            # 指定初始值和初始index
            smallest = list_[0]
            which = 0
            # 只需遍历一次，即可找到最小值和最小的index
            for i in range(1, len(list_)):
                if list_[i] < smallest:
                    smallest, which = list_[i], i
            # 返回最小的index
            return which

        new_list = []
        # 除非原始list被消耗殆尽，否则不停遍历它
        while len(target) > 0:
            # 从旧的列表中删除元素，添加到新的列表中
            new_list.append(target.pop(find_smallest(target)))

        return new_list

    # @ticktock()
    def quick_sort(self, target):
        u"""快速排序."""
        """
        两个需要注意的问题，
        第一个，这里的长度判断，一定是<2，因为指不定就会有空列表传进来.
        随机选择的时候，就随机到了最大值或者最小值
        """
        target = deepcopy(target)
        if len(target) < 2:
            return target
        else:
            smaller, bigger = [], []
            for i in target[1:]:
                """
                第二，这里的判断，一定是带等号的，要不然，我们最终排完序的就少值了啊.
                """
                if i <= target[0]:
                    smaller.append(i)
                elif i > target[0]:
                    bigger.append(i)
            return self.quick_sort(smaller) + [target[0]] + self.quick_sort(bigger)

    @ticktock()
    def test_quick_sort(self, haha):
        u"""测试用，用来显示时间的."""
        return self.quick_sort(haha)
    
    @staticmethod
    def merge_sort(target):
        u"""融合排序."""
        target = deepcopy(target)

@ticktock()
def test_buildin_sort(haha):
    haha = deepcopy(haha)
    haha.sort()
    return haha

def test():
    u"""做测试用的."""
    seed(2)
    ran = [randint(0, 1000) for x in range(1000)]
    test_ = Algorithm()
    # print(binary_search([x for x in range(100000)], 55))
    bubb = test_.bubble_sort(ran)
    slct = test_.selection_sort(ran)
    qick = test_.test_quick_sort(ran)
    buildin = test_buildin_sort(ran)
    # print(test_.sum([x for x in range(10)]))
    print(bubb == slct == qick)

if __name__ == '__main__':
    test()


